//插入排序：逐个遍历，然后和前面已经排序的元素进行比较，插入到对应的位置
//时间复杂度：O(n^2)
function insertionSort(arr) {
  const n = arr.length;
  for (let i = 1; i < n; i++) {
    let j = i - 1;
    const key = arr[i];
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j+1] = key;
  }
  return arr;
}

const arr = [5, 4, 3, 2, 1];
console.log(insertionSort(arr));
